#define _CRT_SECURE_NO_WARNINGS 1
#include"tree.h"
tree* pre = NULL;
tree* last = NULL;
tree* finally = NULL;
void push(tree** root,int x)
{
	assert(root);
	tree* new = (tree*)malloc(sizeof(tree));
	assert(new);
	new->left = NULL;
	new->right = NULL;
	new->val = x;
	if (*root == NULL)
		*root = new;
	else
	{
		if ((*root)->val > x)
			push(&(*root)->left, x);
		else
			push(&(*root)->right, x);
	}
}
tree* find(tree* root, int x)
{
	if (root == NULL)
		return NULL;
	if (x < root->val)
		find(root->left, x);
	else if (root->val == x)
		finally = root;
	else
		find(root->right, x);
} 
static void midp(tree* root, tree* x)
{
	if (root == NULL)
		return;
	else
	{
		midp(root->left, x);
		if (root == x)
			finally = pre;
		pre = root;
		midp(root->right, x);
	}
}
static void midl(tree* root, tree* x)
{
	if (root == NULL)
		return;
	else
	{
		midl(root->left, x);
		if (last == x)
			finally = root;
		last = root;
		midl(root->right, x);
	}
}
void del(tree** root, int x)
{
	assert(root);
	if (*root == NULL)
		return;
	tree* tem = find(*root, x);
	tree* cur = *root;
	while(cur)
	{
		if (x == cur->val)
			break;
		else if (x < cur->val)
			cur = cur->left;
		else
			cur = cur->right;
	}
	if (cur != NULL && cur->left == cur->right)
	{
		midl(*root, tem);
		finally->left = NULL;
		free(tem);
	}
	else if (cur != NULL && cur->left != NULL && cur->right == NULL)
	{
		midl(*root, tem);
		finally->left = tem->left;
		free(tem);
	}
	else if (cur != NULL && cur->left == NULL && cur->right != NULL)
	{
		midp(*root, tem);
		finally->right = tem->right;
		free(tem);
	}
	else
	{
		midp(*root, tem);
		int ret = finally->val;
		tree* prev = finally;
		midp(*root, prev);
		finally->right = NULL;
		free(prev);
		tem->val = ret;
	}
}
void print(tree* root)
{
	if (root == NULL)
		return;
	else
	{
		print(root->left);
		printf("%d->", root->val);
		print(root->right);
	}
}